package org.labuladong.动态规划算法.一维DP;

import java.util.Scanner;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-14:48
 * @Description:
 *
 * 你是⼀个专业的⼩偷，计划偷窃沿街的房屋。这个地⽅所有的房屋都围成⼀
 * 圈，这意味着第⼀个房屋和最后⼀个房屋是紧挨着的。
 * 每间房内都藏有⼀定的现⾦，影响你偷窃的唯⼀制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同⼀晚上被⼩偷闯⼊，系统会⾃动报警。
 * 给定⼀个代表每个房屋存放⾦额的⾮负整数数组，计算你不触动警报装置的情况下，⼀夜之内能够偷窃到的最⾼⾦额。
 * 示例 1：
 * 输⼊：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋（⾦额 = 1)，然后偷窃 3 号房屋（⾦额 = 3)。
 *  偷窃到的最⾼⾦额 = 1 + 3 = 4。
 *
 * @version: 1.0
 */
public class LC_213打家劫舍II {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
//		int[] nums = {1,2,3,1};
		int[] nums = new int[0];
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			nums = new int[n];
			for (int i = 0; i < n; i++) {
				nums[i] = sc.nextInt();
			}
			System.out.println(rob(nums));
		}

	}

	public static int rob(int[] nums) {
		int n = nums.length;
		if (n == 0) return 0;
		if (n == 1) return nums[0];
		if (n == 2) return Math.max(nums[0], nums[1]);

		// 不偷窃第一个房屋的情况
		int[] dpFirst = new int[n];
		dpFirst[0] = 0;
		dpFirst[1] = nums[0];
		for (int i = 2; i <= n; i++) {
			dpFirst[i] = Math.max(dpFirst[i - 1], dpFirst[i - 2] + nums[i - 1]);
		}

		// 偷窃第一个房屋的情况
		int[] dpLast = new int[n];
		dpLast[1] = nums[1]; // 不能偷窃第一个房屋，只能偷窃第二个
		dpLast[2] = Math.max(nums[0], nums[1]);
		for (int i = 2; i < n; i++) {
			dpLast[i] = Math.max(dpLast[i - 1], dpLast[i - 2] + nums[i - 1]);
		}

		// 返回两种情况中的最大值
		return Math.max(dpFirst[n - 1], dpLast[n - 1]);
	}


}
